package com.base.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MinimumTotal {
    public static void main(String[] args) {
        MinimumTotal minimumTotal = new MinimumTotal();
        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(List.of(-1));
        triangle.add(Arrays.asList(2, 3));
        triangle.add(Arrays.asList(1, -1, -3));
        System.out.println(minimumTotal.minimumTotal(triangle));
    }

    private int minimumTotal(List<List<Integer>> triangle) {

        // dp是一维数组 存储当前行的最小路径和 每个元素表示定点到当前行的每个元素的最小路径和 是一个滚动的数据，每遍历一行都会统计当前行的最小值
        int[] dp = new int[triangle.size()];
        dp[0] = triangle.getFirst().getFirst();
        for (int i = 1; i < triangle.size(); i++) {
            // 1
            // 1 1  到当前行每个元素的最小路径和
            // 2 3 4
            // 5 6 7 8
            //当前行需要存储的数据
            int[] temp = new int[triangle.get(i).size()];
            for (int j = 0; j < triangle.get(i).size(); j++) {
                List<Integer> currentLine = triangle.get(i);
                if (j == 0) {
                    //第一个  = 上一行的第一个+当前元素
                    temp[j] = dp[j] + currentLine.get(j);
                } else if (j == triangle.get(i).size() - 1) {
                    //最后一个元素 = 上一行的最后一个+当前元素  上一行比当前行少一个元素
                    temp[j] = dp[j - 1] + currentLine.get(j);
                } else {
                    //中间元素 = 上一行中间元素和前一个元素中的最小值+当前元素
                    temp[j] = Math.min(dp[j - 1], dp[j]) + currentLine.get(j);
                }
            }
            dp = temp;

        }
        int min = Integer.MIN_VALUE;
        for (int j : dp) {
            min = Math.min(min, j);
        }
        return min;
    }

    /**
     *
     * 从倒数第二行开始向上计算
     * @param triangle
     * @return
     */
    private int minimumTotal2(List<List<Integer>> triangle) {
        if (triangle == null || triangle.isEmpty()) {
            return 0;
        }

        // 使用一维数组来存储从底部到当前行的最小路径和
        int[] dp = new int[triangle.size()];

        // 初始化dp数组为最后一行的元素
        for (int i = 0; i < triangle.size(); i++) {
            dp[i] = triangle.getLast().get(i);
        }

        // 从倒数第二行开始向上计算
        for (int i = triangle.size() - 2; i >= 0; i--) {
            List<Integer> currentRow = triangle.get(i);
            for (int j = 0; j < currentRow.size(); j++) {
                // 状态转移方程
                // 1
                // 2 3  计算时：dp[j] = Math.min(dp[j], dp[j + 1]) + currentRow.get(j); 是下一行的相邻的数据比大小
                // 4 5 6
                dp[j] = Math.min(dp[j], dp[j + 1]) + currentRow.get(j);
            }
        }

        // 顶点的最小路径和就是dp[0]
        return dp[0];
    }

}
